package com.leetcode.algorithm.y22.m06;

/**
 * 剑指 Offer II 091. 粉刷房子
 * 
 * https://leetcode.cn/problems/JEj789/
 * 
 * @author jie.deng
 *
 */
class QuestionOffer2091Solution01 {

	public int minCost(int[][] costs) {
		int len = costs.length;
		// DP状态定义
		int[][] dp = new int[len][3];

		// DP状态初始化
		dp[0][0] = costs[0][0];
		dp[0][1] = costs[0][1];
		dp[0][2] = costs[0][2];

		// DP状态转移
		for (int i = 1; i < len; i++) {
			dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
			dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
			dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + costs[i][2];
		}

		int min = Math.min(dp[len - 1][1], dp[len - 1][2]);
		min = Math.min(min, dp[len - 1][0]);
		return min;
	}

}